1. Technical Field
This disclosure relates to a semiconductor device, and more particularly, to a Bose-Chaudhuri-Hocquenghem (BCH) error correction method and circuit capable of correcting an error by using an encoder, thereby reducing a time, power, and the chip layout size required for error correction.
2. Description of the Related Art
FIG. 1 is a block diagram of a conventional semiconductor chip 100 having an error correcting circuit and a flash memory. Referring to FIG. 1, the semiconductor chip 100 includes a flash memory 120 and an error correcting circuit 140. The semiconductor chip 100 may be connected to an external circuit (not shown) via a bus 200. The error correcting circuit 140 includes a control circuit 141, an error correction encoding circuit 142, and an error correction decoding circuit 143.
The error correction encoding circuit 142 receives normal data NDTA that is to be stored in flash memory cell array 120, and generates corresponding parity data PDTA. The normal data NDTA and the parity data PDTA are respectively stored in a normal data region (not shown) and a parity data region (not shown) of the flash memory cell array 120.
The error correction decoding circuit 143 detects and corrects an error in the normal data NDTA when reading the normal data NDTA from the memory cell array 120.
In this case, error correction may be performed using the BCH (Bose-Chaudhuri-Hocquenghem) error correction algorithm. The BCH error correction algorithm is capable of correcting multiple bits of error in a data block, and thus has been widely applied to error correction of communication systems and memory systems.
In particular, in the case of a multi-level cell flash memory device that stores multiple bits in a cell, bit errors are likely to occur. Thus, error correction can be performed using the BCH error correction algorithm capable of correcting multiple bits of error.
Error correction using the BCH algorithm, and particularly, error correction using binary BCH 4148, 4096 code data (hereinafter referred to as “BCH code data”) will be described in detail. Such data is referred to as “BCH code data” or “BCH encoded data”; however, BCH encoded data may have a different length than BCH 4148, 4096 code data.
In general, in error correction using the BCH algorithm, BCH code data is generated using an error correcting encoder, and decoded using an error correcting decoder. Specifically, the BCH code data is decoded by calculating syndromes, constructing an error locator polynomial using the syndromes, and calculating the locations of error bits by obtaining the root of the error locator polynomial. In particular, in order to decode binary BCH code data, an error is corrected by inverting the bit value of an error bit.
FIG. 2 is a conceptual diagram illustrating the format of BCH code data CDATA. Referring to FIG. 2, the BCH code data CDTA consists of 512-byte normal data NDTA and 7-byte parity data PDTA. The parity data PDTA may consist of 48-bit parity and 4-bit dummy data.
FIG. 3 is a diagram illustrating the format of a plurality of pieces of normal data and a plurality of pieces of normal data that are stored within one page of a NAND flash memory. In particular, FIG. 3 illustrates a page PAGE# with a 2K byte normal data region NStorage and 64 byte parity data region PStorage. Accordingly, four pieces of 512-byte normal data NDTA0 through NDTA3 and four pieces of parity data P0 through P3 that are respectively correspond to the normal data NDTA0 through NDTA3, are stored in the page PAGE#.
The BCH code data CDTA is calculated by the error correction encoding circuit 143 of FIG. 1, using an operation on a Galois Field. The BCH code data CDTA consist of the elements of the following primitive polynomial on a Galois Field (GF) 213:P(x)=x13+x4+x3+x+1   (1)
A generation polynomial for generating 4-bit BCH code data on the GF 213 is given by:
                                                                        G                ⁡                                  (                  x                  )                                            =                            ⁢                                                                    g                    52                                    ⁢                                      x                    52                                                  +                                                      g                    51                                    ⁢                                      x                    51                                                  +                …                +                                                      g                    1                                    ⁢                  x                                +                                  g                  0                                                                                                        =                            ⁢                                                x                  52                                +                                  x                  50                                +                                  x                  46                                +                                  x                  44                                +                                  x                  41                                +                                  x                  37                                +                                  x                  36                                +                                  x                  30                                +                                  x                  25                                +                                  x                  24                                +                                  x                  23                                +                                                                                                      ⁢                                                x                  21                                +                                  x                  19                                +                                  x                  17                                +                                  x                  16                                +                                  x                  15                                +                                  x                  10                                +                                  x                  9                                +                                  x                  7                                +                                  x                  5                                +                                  x                  3                                +                x                +                1                                                                        (        2        )            
Random 512-byte normal data NDTA# [d4095, d4094, . . . , d1, d0] may be expressed as the following polynomial:NDTA#=d4095x4095+d4094x+4094+ . . . +d1x+d0   (3)
In this case, remainder bits [R51, R50, . . . , R1, R0] are obtained as parity data by dividing the normal data NDTA# expressed in Equation (3) by the generation polynomial expressed in Equation (2).
A multiplication on the Galois Field may be performed using shift registers. A scheme for generating BCH code data using shift registers is illustrated in FIG. 4.
FIG. 4 is a diagram illustrating an example of the error correction encoding circuit 142, illustrated in FIG. 1, which uses shift registers. Referring to FIG. 4, the error correction encoding circuit 142 includes a plurality of registers r0 through r51, a plurality of XOR gates, and a switch SW. If 4096-bit normal data NDTA [4095:0] are sequentially input to the error correction encoding circuit 142, the bits of parity data are respectively stored in the corresponding registers r0 through r51. The error correction encoding circuit 142 generates 52-bit parity data PDTA[51:0], and parity data PDTA[51:0]) with the input 4096-bit normal data NDTA[4095:0] (that is, it opens a switch SW), and outputs 4148-bit BCH code data CDTA[4147:0].
The error correction encoding circuit as illustrated in FIG. 4 can be embodied in parallel. If the error correction encoding circuit has a parallel structure in which 8 bits are processed at a time, it is possible to produce BCH code data for 4096-bit normal data just within 512 cycles of time.
Referring to FIGS. 1 and 3, the error correction encoding circuit 142 may further include flag registers 145 for error correction, and an RAM block 144 that temporarily stores an “OK” flag, a “FAIL” flag, and data.
The error correction encoding circuit 142 stores first parity data P1 for first normal data NDTA1 in the RAM block 144, and generates second parity data P2 for second normal data NDTA2. If all the first parity data P1 to fourth parity data are generated, 4 pieces of normal data NDTA1 through NDTA4 and the 4 pieces of the parity data P1 through P4 are stored in the flash memory cell array 120.
After the BCH code data is stored, when a read command is received, it is determined whether an error is contained in data that is to be read. If an error exists, the error is corrected, and then, the data is output. Next, a BCH error correction method that uses an error correction decoding circuit when reading data from a memory cell array, will be described.
FIG. 5 is a schematic block diagram of the conventional error correction decoding circuit 143 of FIG. 1. FIG. 6 is a flowchart illustrating a BCH error correction method 600 using the error correction decoding circuit 143 illustrated in FIG. 5.
Referring to FIGS. 5 and 6, the conventional error correction decoding circuit 143 includes a syndrome generator 143a, a Berlekamp-Massey executing unit 143b a Chien search unit 143c, and an error corrector 143d. First, BCH code data CDTA′ stored is input to the syndrome generator 143a of the error correction decoding circuit 143 (operation S610). For convenience of explanation, the BCH code data CDTA′ input to the error correction decoding circuit 143 will now be referred to as “received code data”.
Assuming that the received code data R(x) is [rn-1, rn-2, . . . , r1, r0], the received code data R(x) may be expressed as follows:R(x)=rn-1xn-1+rn-2xn-2+ . . . +r1x+r0,rjεGF(2)   (4)
The syndrome generator 143a produces syndromes, for error checking, from the received code data R(x) expressed in Equation (4) (operation S620). The syndrome generator 143a may produce the syndrome using the following equation:
                                          S            j                    =                                    r              ⁡                              (                                  α                  j                                )                                      =                                          ∑                                  k                  =                  0                                                  n                  -                  1                                            ⁢                                                                    r                    k                                    ⁡                                      (                                          α                      j                                        )                                                  k                                                    ,                  (                                    1              ≤              j              ≤                              2                ⁢                t                                      =                                          2                ×                4                            =              8                                )                                    (        5        )            
It is determined whether an error occurs based on the syndrome Sj illustrated in Equation (5) (operation S630). If an error does not occur, the syndrome Sj has a value of 0. If an error occurs, the syndrome Sj has a value other than 0.
The syndrome generator 143a continuously performs a GF multiplication for calculating Equation (5). However, the syndrome generator 143a applies Equation (5) to each bit of the received code data R(x) expressed in Equation (4). Thus, in order to calculate syndromes for 4148-bit BCH code data, the syndrome generator 143a must perform the GF multiplication 4148 times.
Referring to FIGS. 5 and 6, when an error is detected, the Berlekamp-Massey executing unit 143b calculates an error locator polynomial Λ(α−i) (operation S640). The error locator polynomial Λ(α−i) may be calculated using the Berlekamp-Massey algorithm.
Next, the Chien search unit 143c detects the location of an error bit (operation S650). The location of the error bit may be detected using the Chien search algorithm. The Chien search algorithm detects the location of the error bit, based on whether the error locator polynomial Λ(α−i) has a value of 0. In this case, i represents the location of the error bit. That is, if the error locator polynomial Λ(α−i) has a value of 0, an error occurs in a bit ri of the received code data R(x) expressed in Equation (4).
Similarly to the syndrome generator 143a, the Chien search unit 143c also performs a GF multiplication. Also, for a Chien search for 4148-bit BCH code data, the Chien search unit 143c performs the GF multiplication 4148 times.
If the Chien search reveals the location of the error bit, the error corrector 143d corrects the error (operation S660). As described above, the BCH error correction method 600 using binary BCH code data corrects an error by inverting the bit value of an error bit. In the BCH error correction method 600, if error correction is successfully performed, “OK” flag indicating this fact is output (operation S670). If error correction fails, “FAIL” flag indicating this fact is output (operation S680).
FIG. 7 is a timing diagram of the operation of the error correction decoding circuit 143 of FIG. 5. Referring to FIGS. 5 and 7, although only a short latency with 4 cycles is required to perform the SiBM (Simplified inverse-free Berlekamp-Massey) algorithm, each of syndrome generation and Chien search requires much time due to a 4148-bit long latency. As described above, according to a conventional BCH error correcting circuit and method, for syndrome generation and Chien search, a GF multiplication is needed to be performed a number of times corresponding to the bits of BCH code data.
That is, according to a conventional BCH error correcting circuit and method, a large amount of time and power are required to perform decoding for BCH error correction, thereby degrading the performance of a semiconductor memory device.